817E - Choosing The Commander - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

const int nmax = 1e5;

int q;

struct trieNode{
    trieNode * nxt[2];
    int nr;
    trieNode() : nr(0) {nxt[0] = nxt[1] = nullptr;}
};

struct trie{
    trieNode * root;
    trie(){
        root = new trieNode;
    }
    void insert(int x, int v){
        trieNode * nod = root;
        for(int i = 26; i >= 0; i--){
            if(nod -> nxt[(x >> i) & 1] == nullptr)
                nod -> nxt[(x >> i) & 1] = new trieNode;
            nod = nod -> nxt[(x >> i) & 1];
            nod -> nr += v;
        }
    }
    int cmp(int x, int l){
        trieNode * nod = root;
        int ans = 0;
        for(int i = 26; i >= 0; i--){
            if((l >> i) & 1){
                ans += (nod -> nxt[((x >> i) & 1)] == nullptr ? 0 : nod -> nxt[((x >> i) & 1)] -> nr);
                nod = nod -> nxt[((x >> i) & 1) ^ 1];
            } 
            else{
                nod = nod -> nxt[((x >> i) & 1)];
            }
            if(nod == nullptr)
                return ans;
        }
        return ans;
    }
};

void solve(){
    trie arb;
    cin >> q;
    while(q--){
        int c;
        cin >> c;
        if(c == 1){
            int p;
            cin >> p;
            arb.insert(p, 1);
        }
        else if(c == 2){
            int p;
            cin >> p;
            arb.insert(p, -1);
        }
        else{
            int p, l;
            cin >> p >> l;
            cout << arb.cmp(p, l) << "\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);

    int q = 1;
    // cin >> q;
    while(q--){
        solve();
    }
    return 0;
}